home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000014_icon-group-sender _Sat Dec 17 12:54:04 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  5KB
  1. Received: by cheltenham.cs.arizona.edu; Sat, 17 Dec 1994 04:54:13 MST
  2. Date: Sat, 17 Dec 94 12:54:04 +0100
  3. From: karczma@univ-caen.fr (Jerzy Karczmarczuk)
  4. Message-Id: <9412171154.AA22688@milou.univ-caen.fr>
  5. To: icon-group@cs.arizona.edu
  6. Subject: Backtracking in Icon
  7. Errors-To: icon-group-errors@cs.arizona.edu
  8.  
  9.  
  10. Dave Kuhlman (dkuhlman@netcom) finished his last posting with a 
  11. remark and a question:
  12.  
  13. > Anyway, I'd be interested to know if others use backtracking
  14. > more heavily, or whether maybe this is just a "neat" but
  15. > not so useful feature of Icon.
  16.  
  17. > Or, could it be that the fact that Icon does not have logical
  18. > variables, as Prolog does, make backtracking and goal seeking
  19. > evaluation less usable?
  20.  
  21. John Paolillo (johnp@utafll.uta.edu) decided then to share his
  22. experience:
  23.  
  24. > I have just finished teaching a course "The Computer and Natural Language"
  25. > using Icon.  Through this course, Icon's backtracking became  one of my
  26. > fondest friends, so to speak.
  27.  
  28. ...
  29.  
  30. > Backtracking is an essential
  31. > part of the functioning of such recognizers, and makes it possible 
  32. > to teach linguistics students how to write parsers by applying a 
  33. > simple translation process to get from a formalism they know:
  34.  
  35. >     NP -> (Det) N
  36.  
  37. > ... etc.
  38.  
  39. > I have recently tried to implement something similar in another
  40. > language that I use (because it is visual), which even employs
  41. > failure, but which does not have built-in backtracking.  The result
  42. > was an indescribable mess.  I would rank backtracking among the 
  43. > most important features of Icon for what I do.  There are many 
  44. > many problems you can solve very elegantly with built-in backtracking,
  45. > and once you finally understand it, it is hard to live without.
  46.  
  47.  
  48. A short (?) comment.
  49.  
  50. Backtracking is essential when you use non-deterministic parsing strategies.
  51. For linguists, people who read grammar production rules rather conceptually
  52. than technically, obviously this is a great thing. You won't teach them
  53. the LALR methods, left recursion removal by Greibach normalization, etc.,
  54. unless you want them to strangle you...
  55.  
  56. Unfortunately, in the domain of computer languages, we have a 30 years old
  57. (bad?) tradition - the quest for efficiency, and backtracking is used mainly
  58. for teaching, and not for the parser construction. My students might be
  59. fascinated by the non-deterministic parsers written in Prolog and using
  60. heavily the differential lists, but if they have to write a serious project,
  61. they take YACC...
  62.  
  63. But, fortunately, there are other domains where backtracking may be helpful,
  64. for exemple other kind (than syntaxical) generators: all kind of combinatorial
  65. problems, code-breaking, game playing, task planning etc.  Is the existence
  66. of the logical variable essential? I don't know, but I doubt. The only
  67. place, where this IS essential, and you cannot reproduce this by the reversible
  68. instantation is the usage of incomplete data structures in Prolog, e.g.
  69. the differential lists. But maybe I am wrong.
  70.  
  71. In the Artificial Intelligence domain, when you have to schedule a solution
  72. of a non-deterministic problem, the backtracking IS the only way of doing
  73. it reasonably fast (in terms of human time, not the efficiency of the
  74. algorithm). Then, it is necessary sometimes to memorize a partial solution.
  75. In Prolog this is simply lousy. In Icon this is easier and elegant. I think
  76. that Icon may eventually become more popular thanks to its plethora of data
  77. structures, and the legibility of the programs. But somebody has to write
  78. a serious book showing how to solve real life problems with it. Any takers?
  79.  
  80. Still, another word of critics of  gnikcartkcab:
  81.  
  82. "once you finally understand it, it is hard to live without".
  83.  
  84. No Sir, not necessarily. You may replace the backtracking, whose role is to
  85. provide you an alternative collection of solutions to a given problem, by
  86. a LAZY LIST of these solution. So, the lazy functional languages give you
  87. an alternative. You may find some information about this in quite respectable
  88. books, for example Henderson, or Abelsson&Sussman. 
  89.  
  90. You may wish to read the paper "Painless parsing in Haskell", where this
  91. idea is applied to the syntactic analysis.
  92.  
  93. On the other hand, implementing lazy evaluation in Icon is a real pleasure,
  94. although it is not natural (as the parameters are passed by value), and it
  95. is not very efficient.
  96.  
  97.  
  98. Jerzy Karczmarczuk
  99.  
  100. Dept. d'Informatique, Universite de Caen, Normandy, France.